package com.sunshine.leetcode.hard;

/**
 * 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
 * <p>
 * 示例:
 * <p>
 * 输入: 13
 * 输出: 6
 * 解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-digit-one
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author WeiHong
 * @date 2020/4/24 11:52
 */
public class CountDigitOne {

    /**
     * 1.从1遍历到N，统计1出现的次数
     * 2.考虑比如数字11，统计结果是2
     * 结果：计算超时
     *
     * @param n
     * @return
     */
    public static int myCountDigitOne(int n) {
        int count = 0;
        for (int j = 0; j <= n; j++) {
            String s = String.valueOf(j);
            int[] x = new int[s.length()];
            for (int i = 0; i < s.length(); i++) {
                x[i] = Integer.parseInt(String.valueOf(s.charAt(i)));
            }
            for (int i : x) {
                if (i == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 官方解题
     * 结果：计算错误
     *
     * @param n
     * @return
     */
    public static int countDigitOne(int n) {
        int count = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            count += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);
        }
        return count;
    }

    /**
     * 结果：通过
     *
     * @param n
     * @return
     */
    public int countDigitOne1(int n) {
        int count = 0;
        for (long k = 1; k <= n; k *= 10) {
            long r = n / k, m = n % k;
            count += (r + 8) / 10 * k + (r % 10 == 1 ? m + 1 : 0);
        }
        return count;
    }


}
